package uestc.lj.midPromotion.greedy;

/**
 * @Author:Crazlee
 * @Date:2021/12/6
 */
public class Code06_RemoveDuplicateLettersLessLexi {
	public static String removeDuplicate(String str) {
		if (str == null || str.length() == 0) {
			return str;
		}
		// 词频统计表
		int[] map = new int[256];
		for (int i = 0; i < str.length(); i++) {
			map[str.charAt(i)]++;
		}
		// Asic码最小的位置
		int minAsicIndex = 0;
		for (int i = 0; i < str.length(); i++) {
			if (--map[str.charAt(i)] == 0) {
				break;
			} else {
				minAsicIndex = str.charAt(minAsicIndex) > str.charAt(i) ? i : minAsicIndex;
			}
		}
		// 挑选asic码最小的，同时从当前位置的右边开始挑选，并全部去除当前字符右边的所有相同的当前字符
		return String.valueOf(str.charAt(minAsicIndex) +
				removeDuplicate(str.substring(minAsicIndex + 1).replaceAll(String.valueOf(str.charAt(minAsicIndex)), "")));
	}
}
